{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Basic Calculator IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #recursion #hash-table #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #递归 #哈希表 #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: basicCalculatorIV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #基本计算器 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个表达式如&nbsp;<code>expression = \"e + 8 - a + 5\"</code>&nbsp;和一个求值映射，如&nbsp;<code>{\"e\": 1}</code>（给定的形式为&nbsp;<code>evalvars = [\"e\"]</code> 和&nbsp;<code>evalints = [1]</code>），返回表示简化表达式的标记列表，例如 <code>[\"-1*a\",\"14\"]</code></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>表达式交替使用块和符号，每个块和符号之间有一个空格。</li>\n",
    "\t<li>块要么是括号中的表达式，要么是变量，要么是非负整数。</li>\n",
    "\t<li>变量是一个由小写字母组成的字符串（不包括数字）。请注意，变量可以是多个字母，并注意变量从不具有像&nbsp;<code>\"2x\"</code>&nbsp;或&nbsp;<code>\"-x\"</code>&nbsp;这样的前导系数或一元运算符&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>表达式按通常顺序进行求值：先是括号，然后求乘法，再计算加法和减法。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>expression = \"1 + 2 * 3\"</code>&nbsp;的答案是 <code>[\"7\"]</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>输出格式如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于系数非零的每个自变量项，我们按字典排序的顺序将自变量写在一个项中。\n",
    "\t<ul>\n",
    "\t\t<li>例如，我们永远不会写像 <code>“b*a*c”</code> 这样的项，只写 <code>“a*b*c”</code>。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>项的次数等于被乘的自变量的数目，并计算重复项。我们先写出答案的最大次数项，用字典顺序打破关系，此时忽略词的前导系数。\n",
    "\t<ul>\n",
    "\t\t<li>例如，<code>\"a*a*b*c\"</code> 的次数为 4。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>项的前导系数直接放在左边，用星号将它与变量分隔开(如果存在的话)。前导系数 1 仍然要打印出来。</li>\n",
    "\t<li>格式良好的一个示例答案是&nbsp;<code>[\"-2*a*a*a\", \"3*a*a*b\", \"3*b*b\", \"4*a\", \"5*c\", \"-6\"]</code>&nbsp;。</li>\n",
    "\t<li>系数为 <code>0</code> 的项（包括常数项）不包括在内。\n",
    "\t<ul>\n",
    "\t\t<li>例如，<code>“0”</code> 的表达式输出为&nbsp;<code>[]</code>&nbsp;。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意：</strong>你可以假设给定的表达式均有效。所有中间结果都在区间 <code>[-2<sup>31</sup>, 2<sup>31</sup> - 1]</code> 内。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"e + 8 - a + 5\", evalvars = [\"e\"], evalints = [1]\n",
    "<strong>输出：</strong>[\"-1*a\",\"14\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"e - 8 + temperature - pressure\",\n",
    "evalvars = [\"e\", \"temperature\"], evalints = [1, 12]\n",
    "<strong>输出：</strong>[\"-1*pressure\",\"5\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"(e + 8) * (e - 8)\", evalvars = [], evalints = []\n",
    "<strong>输出：</strong>[\"1*e*e\",\"-64\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= expression.length &lt;= 250</code></li>\n",
    "\t<li><code>expression</code>&nbsp;由小写英文字母，数字&nbsp;<code>'+'</code>,&nbsp;<code>'-'</code>,&nbsp;<code>'*'</code>,&nbsp;<code>'('</code>,&nbsp;<code>')'</code>,&nbsp;<code>' '</code>&nbsp;组成</li>\n",
    "\t<li><code>expression</code>&nbsp;不包含任何前空格或后空格</li>\n",
    "\t<li><code>expression</code>&nbsp;中的所有符号都用一个空格隔开</li>\n",
    "\t<li><code>0 &lt;= evalvars.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= evalvars[i].length &lt;= 20</code></li>\n",
    "\t<li><code>evalvars[i]</code>&nbsp;由小写英文字母组成</li>\n",
    "\t<li><code>evalints.length == evalvars.length</code></li>\n",
    "\t<li><code>-100 &lt;= evalints[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [basic-calculator-iv](https://leetcode.cn/problems/basic-calculator-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [basic-calculator-iv](https://leetcode.cn/problems/basic-calculator-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"e + 8 - a + 5\"\\n[\"e\"]\\n[1]', '\"e - 8 + temperature - pressure\"\\n[\"e\", \"temperature\"]\\n[1, 12]', '\"(e + 8) * (e - 8)\"\\n[]\\n[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections, re\n",
    "\n",
    "class Solution(object):\n",
    "    def basicCalculatorIV(self, expression, evalvars, evalints):\n",
    "        def mult(A, B):\n",
    "            it = list(A.items())\n",
    "            A.clear()\n",
    "            for a, na in it:\n",
    "                for b, nb in B.items():\n",
    "                    A[tuple(sorted(a + b))] += na * nb\n",
    "        lookup = dict(zip(evalvars, evalints))\n",
    "        calc = {'+': collections.Counter.update, '-': collections.Counter.subtract, '*': mult}\n",
    "        data, operator, priority = [], [], {'(': 0, ')': 1, '+': 2, '-': 2, '*': 3}\n",
    "        for m in re.finditer(r'\\(|\\)|\\+|-|\\*|\\w+', expression.join(('(', ')'))):\n",
    "            t = m.group(0)\n",
    "            if t.isdigit():\n",
    "                data.append(collections.Counter({(): int(t)} if int(t) != 0 else {}))\n",
    "            elif t.isalpha():\n",
    "                data.append(collections.Counter({(): lookup[t]} if t in lookup else {(t,): 1}))\n",
    "            else:\n",
    "                while t == ')' and operator[-1] != '(' or \\\n",
    "                (t != '(' and operator and priority[operator[-1]] >= priority[t]):\n",
    "                    calc[operator.pop()](data[-2], data.pop())\n",
    "                t == ')' and operator.pop() or operator.append(t)        \n",
    "        return ['*'.join((str(n),) + x) for x, n in\n",
    "                sorted(data[0].items(), key=lambda x: (-len(x[0]), x[0])) if n != 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        # 需要递归处理小括号\n",
    "        # 需要考虑先乘，后加减\n",
    "        # 用dict()存储每个值\n",
    "        # 其中常数表示为{'1':3}\n",
    "\n",
    "        # 将expression用空格分开\n",
    "        # 当运算符号是*时,计算\n",
    "        # 当运算符号是+-时,暂时不计算,达到5项(2个运算符号时)再计算第一个符号\n",
    "        \n",
    "        maps = dict()\n",
    "        for var,val in zip(evalvars,evalints):\n",
    "            maps[var] = val\n",
    "        # 在(右侧加上空格\n",
    "        # 在)左侧加上空格\n",
    "        # 于是()就类似于一种运算符号了\n",
    "        arr = list(expression)\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == '(':\n",
    "                arr[i] = '( '\n",
    "            elif arr[i] == ')':\n",
    "                arr[i] = ' )'\n",
    "        expression = ''.join(arr)\n",
    "\n",
    "        def f(exp):    # 将字符串分割成数组,并且格式化\n",
    "            exp = exp.split()\n",
    "            ans = list()\n",
    "            for i in range(len(exp)):\n",
    "                if exp[i] in maps:\n",
    "                    exp[i] = str(maps[exp[i]])\n",
    "                if exp[i].isdecimal() or (exp[i][0] == '-' and exp[i][1:].isdecimal()):\n",
    "                    ans.append({'1':int(exp[i])})\n",
    "                elif exp[i] in ('+','-','*','(',')'):\n",
    "                    ans.append(exp[i])\n",
    "                else:\n",
    "                    ans.append({exp[i]:1})\n",
    "            return ans\n",
    "        \n",
    "        expression = f(expression)\n",
    "\n",
    "        #print(expression)\n",
    "        def mult(d1,d2):\n",
    "            ret = dict()\n",
    "            for k1,v1 in d1.items():\n",
    "                for k2,v2 in d2.items():\n",
    "                    if k1 == '1':\n",
    "                        newKey = k2\n",
    "                    elif k2 == '1':\n",
    "                        newKey = k1\n",
    "                    else:\n",
    "                        newKey = '*'.join(sorted(k1.split('*') + k2.split('*')))\n",
    "                    ret[newKey] = ret.get(newKey,0) + v1 * v2\n",
    "            return ret\n",
    "        \n",
    "        def OPadd(d1,d2):\n",
    "            ret = dict()\n",
    "            for k,v in d1.items():\n",
    "                ret[k] = v\n",
    "            for k,v in d2.items():\n",
    "                ret[k] = ret.get(k,0) + v\n",
    "            return ret\n",
    "        \n",
    "        def OPsub(d1,d2):\n",
    "            ret = dict()\n",
    "            for k,v in d1.items():\n",
    "                ret[k] = v\n",
    "            for k,v in d2.items():\n",
    "                ret[k] = ret.get(k,0) - v\n",
    "            return ret\n",
    "\n",
    "        def calc3(ans): # 返回list\n",
    "            match ans[1]:\n",
    "                case '+':\n",
    "                    ans = [OPadd(ans[0],ans[2])]\n",
    "                case '-':\n",
    "                    ans = [OPsub(ans[0],ans[2])]\n",
    "                case '*':\n",
    "                    ans = [mult(ans[0],ans[2])]\n",
    "            return ans\n",
    "\n",
    "        def calc5(ans): # 返回list\n",
    "            if ans[-2] == '*':\n",
    "                ans = ans[:-3] + [mult(ans[-3],ans[-1])]\n",
    "            else:\n",
    "                if ans[1] == '+':\n",
    "                    ans = [OPadd(ans[0],ans[2])] + ans[3:]\n",
    "                elif ans[1] == '-':\n",
    "                    ans = [OPsub(ans[0],ans[2])] + ans[3:]\n",
    "            return ans\n",
    "\n",
    "        def calc(ans): # 返回list\n",
    "            if len(ans) == 3:\n",
    "                if ans[1] == '*':\n",
    "                    return calc3(ans)\n",
    "            elif len(ans) == 5:\n",
    "                return calc5(ans)\n",
    "            return ans\n",
    "        \n",
    "        def calcFinal(ans): # 返回dict\n",
    "            #print('final',ans)\n",
    "            if len(ans) == 3:\n",
    "                return calc3(ans)[0]\n",
    "            elif len(ans) == 5:\n",
    "                return calc3(calc5(ans))[0]\n",
    "            else:\n",
    "                return ans[0]\n",
    "\n",
    "        def helper(expression,idx):    # 返回从idx开始的计算结果(dict) 和 当前公式的结尾位置\n",
    "            #print(expression,idx)\n",
    "            i = idx\n",
    "            ans = list()\n",
    "            while i < len(expression):\n",
    "                if expression[i] == '(':\n",
    "                    val,tail = helper(expression,i + 1)\n",
    "                    ans.append(val)\n",
    "                    i = tail\n",
    "                elif expression[i] == ')':\n",
    "                    return calcFinal(ans),i\n",
    "                else:\n",
    "                    ans.append(expression[i])\n",
    "                ans = calc(ans)\n",
    "                #print(ans)\n",
    "                i += 1\n",
    "            return calcFinal(ans),i\n",
    "        \n",
    "        ansDict,_ = helper(expression,0)\n",
    "        #print(ansDict)\n",
    "        ans = list()\n",
    "        for k in sorted(ansDict.keys(),key = lambda x:(-len(x.split('*')),x)):\n",
    "            if ansDict[k] == 0:\n",
    "                continue\n",
    "            if k == '1':\n",
    "                continue\n",
    "            else:\n",
    "                ans.append(str(ansDict[k]) + '*' + k)\n",
    "        if '1' in ansDict and ansDict['1'] != 0:\n",
    "            ans.append(str(ansDict['1']))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        # 通用双栈+全局分词+元组计数字典+处理首尾括号+排除计数0\n",
    "        # 计数字典的key是元组, 方便排序处理, 其中空元组代表常量\n",
    "        maps = {}\n",
    "        for v, i in zip(evalvars, evalints):\n",
    "            maps[v] = i\n",
    "        # 全局按照空格分词\n",
    "        tokens = expression.split()\n",
    "        # 操作符的优先级\n",
    "        pri = {\n",
    "            \"(\": 0,\n",
    "            \"+\": 1,\n",
    "            \"-\": 1,\n",
    "            \"*\": 2,\n",
    "        }\n",
    "        # 数字栈和符号栈\n",
    "        numStack, opStack = [], []\n",
    "\n",
    "        def calTwo():\n",
    "            # 计算栈顶\n",
    "            if len(numStack) < 2 or len(opStack) < 1:\n",
    "                return\n",
    "            op = opStack.pop()\n",
    "            b = numStack.pop()\n",
    "            a = numStack.pop()\n",
    "            c = collections.defaultdict(int)\n",
    "            if op == \"*\":\n",
    "                # 两重循环求乘积\n",
    "                for k1 in a:\n",
    "                    for k2 in b:\n",
    "                        # 新的key要按照字典序排序\n",
    "                        k = tuple(sorted(k1 + k2))\n",
    "                        # 新的计数是原计数相乘\n",
    "                        c[k] += a[k1] * b[k2]\n",
    "            else:\n",
    "                # 求和或求差\n",
    "                c = a.copy()\n",
    "                for k in b:\n",
    "                    if op == \"+\":\n",
    "                        c[k] += b[k]\n",
    "                    else:\n",
    "                        c[k] -= b[k]\n",
    "            numStack.append(c)\n",
    "\n",
    "        def convert(token):\n",
    "            # 将当前分词转换成元组计数字典\n",
    "            d = collections.defaultdict(int)\n",
    "            # 注意key都是元组, 常量是空元组, 变量是包含自身的元组\n",
    "            if token in maps:\n",
    "                d[()] = maps[token]\n",
    "            elif token.isnumeric():\n",
    "                d[()] = int(token)\n",
    "            else:\n",
    "                d[(token,)] = 1\n",
    "            return d\n",
    "\n",
    "        for t in tokens:\n",
    "            if t in pri:\n",
    "                # 当前token是操作符\n",
    "                op = t\n",
    "                while opStack and pri[opStack[-1]] >= pri[op]:\n",
    "                    # 栈顶优先级更高, 先计算它\n",
    "                    calTwo()\n",
    "                opStack.append(op)\n",
    "            else:\n",
    "                # 先处理首尾括号, 注意括号都可能有多个, 且可以同时存在于一个token中\n",
    "                # 例如((a + b) * (c + d)) + (e)\n",
    "                # 左右非括号边界\n",
    "                l, r = 0, len(t) - 1\n",
    "                # 右括号数目\n",
    "                rcnt = 0\n",
    "                while l < r and t[l] == \"(\":\n",
    "                    # 将左括号压入栈中\n",
    "                    opStack.append(\"(\")\n",
    "                    l += 1\n",
    "                while l < r and t[r] == \")\":\n",
    "                    rcnt += 1\n",
    "                    r -= 1\n",
    "                # 处理完括号后, 剩余部分转换后压入栈中\n",
    "                numStack.append(convert(t[l : r + 1]))\n",
    "                while rcnt > 0:\n",
    "                    # 循环处理累积的右括号, 不断弹出并计算栈顶, 直到栈顶是最近的左括号\n",
    "                    while opStack and opStack[-1] != \"(\":\n",
    "                        calTwo()\n",
    "                    # 注意当前栈顶是左括号, 需要额外将其弹出\n",
    "                    opStack.pop()\n",
    "                    rcnt -= 1\n",
    "\n",
    "        while opStack:\n",
    "            # 如果仍有剩余的操作数, 计算它们\n",
    "            calTwo()\n",
    "        # 栈中唯一元素即为最终的元组计数字典\n",
    "        d = numStack[0]\n",
    "        res = []\n",
    "        # 将key按照长度递减, 字母递增的顺序排列\n",
    "        skeys = sorted(d.keys(), key=lambda t: (-len(t), t))\n",
    "        for k in skeys:\n",
    "            cnt = d[k]\n",
    "            if cnt != 0:\n",
    "                # 注意排除计数为0的项!!!\n",
    "                key = \"*\".join(k)\n",
    "                # 如果是常数, 则key是空字符串, 不带*\n",
    "                item = f\"{cnt}*{key}\" if key != \"\" else str(cnt)\n",
    "                res.append(item)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Poly(Counter):\n",
    "    def __add__(self,other):\n",
    "        self.update(other)\n",
    "        return self\n",
    "    def __sub__(self,other):\n",
    "        self.update({k:-v for k,v in other.items()})\n",
    "        return self\n",
    "    def __mul__(self,other):\n",
    "        ans = Poly()\n",
    "        for k1,v1 in self.items():\n",
    "            for k2,v2 in other.items():\n",
    "                ans.update({tuple(sorted(k1+k2)):v1*v2})\n",
    "        return ans\n",
    "    def evaluate(self, evalmap):\n",
    "        ans = Poly()\n",
    "        for k,c in self.items():\n",
    "            free = []\n",
    "            for token in k:\n",
    "                if token in evalmap:\n",
    "                    c *= evalmap[token]\n",
    "                else:\n",
    "                    free.append(token)\n",
    "            ans[tuple(free)] += c\n",
    "        return ans\n",
    " \n",
    "    def to_list(self):\n",
    "        return [\"*\".join((str(v),) + k)\n",
    "                for k, v in sorted(self.items(),\n",
    "                    key = lambda x: (-len(x[0]), x[0], x[1]))\n",
    "                if v]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        evalmap = dict(zip(evalvars,evalints))\n",
    "\n",
    "        def combine(left,right,symbol):\n",
    "            if symbol == '+':return left+right\n",
    "            if symbol == '-':return left-right\n",
    "            if symbol == '*':return left*right\n",
    "\n",
    "        def make(expr):\n",
    "            ans = Poly()\n",
    "            if expr.isdigit():\n",
    "                ans.update({():int(expr)})\n",
    "            else:\n",
    "                ans[tuple([expr])] += 1\n",
    "            return ans\n",
    "        \n",
    "        def parse(expr):\n",
    "            bucket = []\n",
    "            symbols = []\n",
    "            i = 0\n",
    "            while i<len(expr):\n",
    "                if expr[i] == '(':\n",
    "                    bal = 0\n",
    "                    for j in range(i,len(expr)):\n",
    "                        if expr[j] == '(':bal+=1\n",
    "                        if expr[j] == ')':bal-=1\n",
    "                        if bal == 0:break\n",
    "                    \n",
    "                    try:\n",
    "                        bucket.append(parse(expr[i+1:j]))\n",
    "                    except Exception as e:\n",
    "                        print(expr[i+1:j])\n",
    "                    i = j\n",
    "                elif expr[i].isalnum():\n",
    "                    for j in range(i,len(expr)):\n",
    "                        if expr[j]==' ':\n",
    "                            bucket.append(make(expr[i:j]))\n",
    "                            break\n",
    "                    else:\n",
    "                        bucket.append(make(expr[i:]))\n",
    "                    i = j\n",
    "                elif expr[i] in \"+-*\":\n",
    "                    symbols.append(expr[i])\n",
    "                i += 1\n",
    "            \n",
    "            for i in range(len(symbols)-1,-1,-1):\n",
    "                if symbols[i] == '*':\n",
    "                    bucket[i] = combine(bucket[i], bucket.pop(i+1),symbols.pop(i))\n",
    "   \n",
    "            ans = bucket[0]\n",
    "            for i,symbol in enumerate(symbols,1):\n",
    "                ans = combine(ans,bucket[i],symbol)\n",
    "            return ans\n",
    "\n",
    "        P = parse(expression).evaluate(evalmap)\n",
    "        return P.to_list()\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        # 需要递归处理小括号\n",
    "        # 需要考虑先乘，后加减\n",
    "        # 用dict()存储每个值\n",
    "        # 其中常数表示为{'1':3}\n",
    "\n",
    "        # 将expression用空格分开\n",
    "        # 当运算符号是*时,计算\n",
    "        # 当运算符号是+-时,暂时不计算,达到5项(2个运算符号时)再计算第一个符号\n",
    "        \n",
    "        maps = dict()\n",
    "        for var,val in zip(evalvars,evalints):\n",
    "            maps[var] = val\n",
    "        # 在(右侧加上空格\n",
    "        # 在)左侧加上空格\n",
    "        # 于是()就类似于一种运算符号了\n",
    "        arr = list(expression)\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == '(':\n",
    "                arr[i] = '( '\n",
    "            elif arr[i] == ')':\n",
    "                arr[i] = ' )'\n",
    "        expression = ''.join(arr)\n",
    "\n",
    "        def f(exp):    # 将字符串分割成数组,并且格式化\n",
    "            exp = exp.split()\n",
    "            ans = list()\n",
    "            for i in range(len(exp)):\n",
    "                if exp[i] in maps:\n",
    "                    exp[i] = str(maps[exp[i]])\n",
    "                if exp[i].isdecimal() or (exp[i][0] == '-' and exp[i][1:].isdecimal()):\n",
    "                    ans.append({'1':int(exp[i])})\n",
    "                elif exp[i] in ('+','-','*','(',')'):\n",
    "                    ans.append(exp[i])\n",
    "                else:\n",
    "                    ans.append({exp[i]:1})\n",
    "            return ans\n",
    "        \n",
    "        expression = f(expression)\n",
    "\n",
    "        #print(expression)\n",
    "        def mult(d1,d2):\n",
    "            ret = dict()\n",
    "            for k1,v1 in d1.items():\n",
    "                for k2,v2 in d2.items():\n",
    "                    if k1 == '1':\n",
    "                        newKey = k2\n",
    "                    elif k2 == '1':\n",
    "                        newKey = k1\n",
    "                    else:\n",
    "                        newKey = '*'.join(sorted(k1.split('*') + k2.split('*')))\n",
    "                    ret[newKey] = ret.get(newKey,0) + v1 * v2\n",
    "            return ret\n",
    "        \n",
    "        def OPadd(d1,d2):\n",
    "            ret = dict()\n",
    "            for k,v in d1.items():\n",
    "                ret[k] = v\n",
    "            for k,v in d2.items():\n",
    "                ret[k] = ret.get(k,0) + v\n",
    "            return ret\n",
    "        \n",
    "        def OPsub(d1,d2):\n",
    "            ret = dict()\n",
    "            for k,v in d1.items():\n",
    "                ret[k] = v\n",
    "            for k,v in d2.items():\n",
    "                ret[k] = ret.get(k,0) - v\n",
    "            return ret\n",
    "\n",
    "        def calc3(ans): # 返回list\n",
    "            match ans[1]:\n",
    "                case '+':\n",
    "                    ans = [OPadd(ans[0],ans[2])]\n",
    "                case '-':\n",
    "                    ans = [OPsub(ans[0],ans[2])]\n",
    "                case '*':\n",
    "                    ans = [mult(ans[0],ans[2])]\n",
    "            return ans\n",
    "\n",
    "        def calc5(ans): # 返回list\n",
    "            if ans[-2] == '*':\n",
    "                ans = ans[:-3] + [mult(ans[-3],ans[-1])]\n",
    "            else:\n",
    "                if ans[1] == '+':\n",
    "                    ans = [OPadd(ans[0],ans[2])] + ans[3:]\n",
    "                elif ans[1] == '-':\n",
    "                    ans = [OPsub(ans[0],ans[2])] + ans[3:]\n",
    "            return ans\n",
    "\n",
    "        def calc(ans): # 返回list\n",
    "            if len(ans) == 3:\n",
    "                if ans[1] == '*':\n",
    "                    return calc3(ans)\n",
    "            elif len(ans) == 5:\n",
    "                return calc5(ans)\n",
    "            return ans\n",
    "        \n",
    "        def calcFinal(ans): # 返回dict\n",
    "            #print('final',ans)\n",
    "            if len(ans) == 3:\n",
    "                return calc3(ans)[0]\n",
    "            elif len(ans) == 5:\n",
    "                return calc3(calc5(ans))[0]\n",
    "            else:\n",
    "                return ans[0]\n",
    "\n",
    "        def helper(expression,idx):    # 返回从idx开始的计算结果(dict) 和 当前公式的结尾位置\n",
    "            #print(expression,idx)\n",
    "            i = idx\n",
    "            ans = list()\n",
    "            while i < len(expression):\n",
    "                if expression[i] == '(':\n",
    "                    val,tail = helper(expression,i + 1)\n",
    "                    ans.append(val)\n",
    "                    i = tail\n",
    "                elif expression[i] == ')':\n",
    "                    return calcFinal(ans),i\n",
    "                else:\n",
    "                    ans.append(expression[i])\n",
    "                ans = calc(ans)\n",
    "                #print(ans)\n",
    "                i += 1\n",
    "            return calcFinal(ans),i\n",
    "        \n",
    "        ansDict,_ = helper(expression,0)\n",
    "        #print(ansDict)\n",
    "        ans = list()\n",
    "        for k in sorted(ansDict.keys(),key = lambda x:(-len(x.split('*')),x)):\n",
    "            if ansDict[k] == 0:\n",
    "                continue\n",
    "            if k == '1':\n",
    "                continue\n",
    "            else:\n",
    "                ans.append(str(ansDict[k]) + '*' + k)\n",
    "        if '1' in ansDict and ansDict['1'] != 0:\n",
    "            ans.append(str(ansDict['1']))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Poly:\n",
    "    def __init__(self):\n",
    "        self.d = defaultdict(int)\n",
    "\n",
    "    def add(self, x):\n",
    "        for k, v in x.items():\n",
    "            self.d[k] += v\n",
    "\n",
    "    def sub(self, x):\n",
    "        for k, v in x.items():\n",
    "            self.d[k] -= v\n",
    "\n",
    "    def mul(self, x):\n",
    "        tmp = defaultdict(int)\n",
    "        for k1, v1 in self.d.items():\n",
    "            for k2, v2 in x.items():\n",
    "                tmp[tuple(sorted(k1 + k2))] += v1 * v2\n",
    "\n",
    "        self.d = tmp\n",
    "\n",
    "    def evaluate(self, m):\n",
    "        tmp = defaultdict(int)\n",
    "        for k, v in self.d.items():\n",
    "            s = []\n",
    "            for kk in k:\n",
    "                if kk in m:\n",
    "                    v *= m[kk]\n",
    "                else:\n",
    "                    s.append(kk)\n",
    "\n",
    "            tmp[tuple(s)] += v\n",
    "\n",
    "        self.d = tmp\n",
    "\n",
    "    def to_list(self):\n",
    "        ret = []\n",
    "        for k in sorted(self.d.keys(), key=lambda x: (-len(x), x)):\n",
    "            if k != () and self.d[k] != 0:\n",
    "                ret.append('*'.join((str(self.d[k]),) + k))\n",
    "\n",
    "        if () in self.d and self.d[()] != 0:\n",
    "            ret.append(str(self.d[()]))\n",
    "        \n",
    "        return ret\n",
    "\n",
    "    def __repr__(self):\n",
    "        return str(self.d)\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        tokens = [x for x in re.split(r'([\\(\\)\\+\\-\\*])', expression.replace(' ', '')) if x != '']\n",
    "\n",
    "        n = len(tokens)\n",
    "\n",
    "        values = dict(zip(evalvars, evalints))\n",
    "\n",
    "        def combine(left, right, symbol):\n",
    "            if symbol == '+':\n",
    "                left.add(right.d)\n",
    "            elif symbol == '-':\n",
    "                left.sub(right.d)\n",
    "            elif symbol == '*':\n",
    "                left.mul(right.d)\n",
    "\n",
    "            return left\n",
    "\n",
    "        def make(i):\n",
    "            expr = tokens[i]\n",
    "            ret = Poly()\n",
    "            if expr.isdigit():\n",
    "                ret.add({\n",
    "                    (): int(expr)\n",
    "                })\n",
    "            else:\n",
    "                ret.add({\n",
    "                    (expr,): 1\n",
    "                })\n",
    "            return ret\n",
    "\n",
    "        def parse(i):\n",
    "            bucket = []\n",
    "            symbols = []\n",
    "\n",
    "            while i < n:\n",
    "                if tokens[i] == '(':\n",
    "                    j, ret = parse(i + 1)\n",
    "                    bucket.append(ret)\n",
    "                    i = j\n",
    "                elif tokens[i] == ')':\n",
    "                    break\n",
    "                elif tokens[i] in '+-*':\n",
    "                    symbols.append(tokens[i])\n",
    "                else:\n",
    "                    bucket.append(make(i))\n",
    "\n",
    "                i += 1\n",
    "\n",
    "            idx = i\n",
    "\n",
    "            if not bucket:\n",
    "                return idx, Poly()    \n",
    "\n",
    "            for i in range(len(symbols) - 1, -1, -1):\n",
    "                if symbols[i] == '*':\n",
    "                    bucket[i] = combine(bucket[i], bucket.pop(i + 1), symbols.pop(i))\n",
    "\n",
    "            ret = bucket[0]\n",
    "\n",
    "            for i, s in enumerate(symbols, 1):\n",
    "                ret = combine(ret, bucket[i], s)\n",
    "\n",
    "            return idx, ret\n",
    "\n",
    "        _, ret = parse(0)\n",
    "\n",
    "        ret.evaluate(values)\n",
    "\n",
    "        return ret.to_list()\n",
    "            \n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        # 需要递归处理小括号\n",
    "        # 需要考虑先乘，后加减\n",
    "        # 用dict()存储每个值\n",
    "        # 其中常数表示为{'1':3}\n",
    "\n",
    "        # 将expression用空格分开\n",
    "        # 当运算符号是*时,计算\n",
    "        # 当运算符号是+-时,暂时不计算,达到5项(2个运算符号时)再计算第一个符号\n",
    "        \n",
    "        maps = dict()\n",
    "        for var,val in zip(evalvars,evalints):\n",
    "            maps[var] = val\n",
    "        # 在(右侧加上空格\n",
    "        # 在)左侧加上空格\n",
    "        # 于是()就类似于一种运算符号了\n",
    "        arr = list(expression)\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == '(':\n",
    "                arr[i] = '( '\n",
    "            elif arr[i] == ')':\n",
    "                arr[i] = ' )'\n",
    "        expression = ''.join(arr)\n",
    "\n",
    "        def f(exp):    # 将字符串分割成数组,并且格式化\n",
    "            exp = exp.split()\n",
    "            ans = list()\n",
    "            for i in range(len(exp)):\n",
    "                if exp[i] in maps:\n",
    "                    exp[i] = str(maps[exp[i]])\n",
    "                if exp[i].isdecimal() or (exp[i][0] == '-' and exp[i][1:].isdecimal()):\n",
    "                    ans.append({'1':int(exp[i])})\n",
    "                elif exp[i] in ('+','-','*','(',')'):\n",
    "                    ans.append(exp[i])\n",
    "                else:\n",
    "                    ans.append({exp[i]:1})\n",
    "            return ans\n",
    "        \n",
    "        expression = f(expression)\n",
    "\n",
    "        #print(expression)\n",
    "        def mult(d1,d2):\n",
    "            ret = dict()\n",
    "            for k1,v1 in d1.items():\n",
    "                for k2,v2 in d2.items():\n",
    "                    if k1 == '1':\n",
    "                        newKey = k2\n",
    "                    elif k2 == '1':\n",
    "                        newKey = k1\n",
    "                    else:\n",
    "                        newKey = '*'.join(sorted(k1.split('*') + k2.split('*')))\n",
    "                    ret[newKey] = ret.get(newKey,0) + v1 * v2\n",
    "            return ret\n",
    "        \n",
    "        def OPadd(d1,d2):\n",
    "            ret = dict()\n",
    "            for k,v in d1.items():\n",
    "                ret[k] = v\n",
    "            for k,v in d2.items():\n",
    "                ret[k] = ret.get(k,0) + v\n",
    "            return ret\n",
    "        \n",
    "        def OPsub(d1,d2):\n",
    "            ret = dict()\n",
    "            for k,v in d1.items():\n",
    "                ret[k] = v\n",
    "            for k,v in d2.items():\n",
    "                ret[k] = ret.get(k,0) - v\n",
    "            return ret\n",
    "\n",
    "        def calc3(ans): # 返回list\n",
    "            match ans[1]:\n",
    "                case '+':\n",
    "                    ans = [OPadd(ans[0],ans[2])]\n",
    "                case '-':\n",
    "                    ans = [OPsub(ans[0],ans[2])]\n",
    "                case '*':\n",
    "                    ans = [mult(ans[0],ans[2])]\n",
    "            return ans\n",
    "\n",
    "        def calc5(ans): # 返回list\n",
    "            if ans[-2] == '*':\n",
    "                ans = ans[:-3] + [mult(ans[-3],ans[-1])]\n",
    "            else:\n",
    "                if ans[1] == '+':\n",
    "                    ans = [OPadd(ans[0],ans[2])] + ans[3:]\n",
    "                elif ans[1] == '-':\n",
    "                    ans = [OPsub(ans[0],ans[2])] + ans[3:]\n",
    "            return ans\n",
    "\n",
    "        def calc(ans): # 返回list\n",
    "            if len(ans) == 3:\n",
    "                if ans[1] == '*':\n",
    "                    return calc3(ans)\n",
    "            elif len(ans) == 5:\n",
    "                return calc5(ans)\n",
    "            return ans\n",
    "        \n",
    "        def calcFinal(ans): # 返回dict\n",
    "            #print('final',ans)\n",
    "            if len(ans) == 3:\n",
    "                return calc3(ans)[0]\n",
    "            elif len(ans) == 5:\n",
    "                return calc3(calc5(ans))[0]\n",
    "            else:\n",
    "                return ans[0]\n",
    "\n",
    "        def helper(expression,idx):    # 返回从idx开始的计算结果(dict) 和 当前公式的结尾位置\n",
    "            #print(expression,idx)\n",
    "            i = idx\n",
    "            ans = list()\n",
    "            while i < len(expression):\n",
    "                if expression[i] == '(':\n",
    "                    val,tail = helper(expression,i + 1)\n",
    "                    ans.append(val)\n",
    "                    i = tail\n",
    "                elif expression[i] == ')':\n",
    "                    return calcFinal(ans),i\n",
    "                else:\n",
    "                    ans.append(expression[i])\n",
    "                ans = calc(ans)\n",
    "                #print(ans)\n",
    "                i += 1\n",
    "            return calcFinal(ans),i\n",
    "        \n",
    "        ansDict,_ = helper(expression,0)\n",
    "        #print(ansDict)\n",
    "        ans = list()\n",
    "        for k in sorted(ansDict.keys(),key = lambda x:(-len(x.split('*')),x)):\n",
    "            if ansDict[k] == 0:\n",
    "                continue\n",
    "            if k == '1':\n",
    "                continue\n",
    "            else:\n",
    "                ans.append(str(ansDict[k]) + '*' + k)\n",
    "        if '1' in ansDict and ansDict['1'] != 0:\n",
    "            ans.append(str(ansDict['1']))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        # 在小括号前后添加空格,使其像一个运算符一样被处理,可以简化很多操作\n",
    "        \n",
    "        # 需要递归处理小括号\n",
    "        # 需要考虑先乘，后加减\n",
    "        # 用dict()存储每个值\n",
    "        # 其中常数表示为{'1':3}\n",
    "\n",
    "        # 将expression用空格分开\n",
    "        # 当运算符号是*时,计算\n",
    "        # 当运算符号是+-时,暂时不计算,达到5项(2个运算符号时)再计算第一个符号\n",
    "        \n",
    "        maps = dict()\n",
    "        for var,val in zip(evalvars,evalints):\n",
    "            maps[var] = val\n",
    "        # 在(右侧加上空格\n",
    "        # 在)左侧加上空格\n",
    "        # 于是()就类似于一种运算符号了\n",
    "        arr = list(expression)\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == '(':\n",
    "                arr[i] = '( '\n",
    "            elif arr[i] == ')':\n",
    "                arr[i] = ' )'\n",
    "        expression = ''.join(arr)\n",
    "\n",
    "        def f(exp):    # 将字符串分割成数组,并且格式化\n",
    "            exp = exp.split()\n",
    "            ans = list()\n",
    "            for i in range(len(exp)):\n",
    "                if exp[i] in maps:\n",
    "                    exp[i] = str(maps[exp[i]])\n",
    "                if exp[i].isdecimal() or (exp[i][0] == '-' and exp[i][1:].isdecimal()):\n",
    "                    ans.append({'1':int(exp[i])})\n",
    "                elif exp[i] in ('+','-','*','(',')'):\n",
    "                    ans.append(exp[i])\n",
    "                else:\n",
    "                    ans.append({exp[i]:1})\n",
    "            return ans\n",
    "        \n",
    "        expression = f(expression)\n",
    "\n",
    "        #print(expression)\n",
    "        def mult(d1,d2):\n",
    "            ret = dict()\n",
    "            for k1,v1 in d1.items():\n",
    "                for k2,v2 in d2.items():\n",
    "                    if k1 == '1':\n",
    "                        newKey = k2\n",
    "                    elif k2 == '1':\n",
    "                        newKey = k1\n",
    "                    else:\n",
    "                        newKey = '*'.join(sorted(k1.split('*') + k2.split('*')))\n",
    "                    ret[newKey] = ret.get(newKey,0) + v1 * v2\n",
    "            return ret\n",
    "        \n",
    "        def OPadd(d1,d2):\n",
    "            ret = dict()\n",
    "            for k,v in d1.items():\n",
    "                ret[k] = v\n",
    "            for k,v in d2.items():\n",
    "                ret[k] = ret.get(k,0) + v\n",
    "            return ret\n",
    "        \n",
    "        def OPsub(d1,d2):\n",
    "            ret = dict()\n",
    "            for k,v in d1.items():\n",
    "                ret[k] = v\n",
    "            for k,v in d2.items():\n",
    "                ret[k] = ret.get(k,0) - v\n",
    "            return ret\n",
    "\n",
    "        def calc3(ans): # 返回list\n",
    "            match ans[1]:\n",
    "                case '+':\n",
    "                    ans = [OPadd(ans[0],ans[2])]\n",
    "                case '-':\n",
    "                    ans = [OPsub(ans[0],ans[2])]\n",
    "                case '*':\n",
    "                    ans = [mult(ans[0],ans[2])]\n",
    "            return ans\n",
    "\n",
    "        def calc5(ans): # 返回list\n",
    "            if ans[-2] == '*':\n",
    "                ans = ans[:-3] + [mult(ans[-3],ans[-1])]\n",
    "            else:\n",
    "                if ans[1] == '+':\n",
    "                    ans = [OPadd(ans[0],ans[2])] + ans[3:]\n",
    "                elif ans[1] == '-':\n",
    "                    ans = [OPsub(ans[0],ans[2])] + ans[3:]\n",
    "            return ans\n",
    "\n",
    "        def calc(ans): # 返回list\n",
    "            if len(ans) == 3:\n",
    "                if ans[1] == '*':\n",
    "                    return calc3(ans)\n",
    "            elif len(ans) == 5:\n",
    "                return calc5(ans)\n",
    "            return ans\n",
    "        \n",
    "        def calcFinal(ans): # 返回dict\n",
    "            #print('final',ans)\n",
    "            if len(ans) == 3:\n",
    "                return calc3(ans)[0]\n",
    "            elif len(ans) == 5:\n",
    "                return calc3(calc5(ans))[0]\n",
    "            else:\n",
    "                return ans[0]\n",
    "\n",
    "        def helper(expression,idx):    # 返回从idx开始的计算结果(dict) 和 当前公式的结尾位置\n",
    "            #print(expression,idx)\n",
    "            i = idx\n",
    "            ans = list()\n",
    "            while i < len(expression):\n",
    "                if expression[i] == '(':\n",
    "                    val,tail = helper(expression,i + 1)\n",
    "                    ans.append(val)\n",
    "                    i = tail\n",
    "                elif expression[i] == ')':\n",
    "                    return calcFinal(ans),i\n",
    "                else:\n",
    "                    ans.append(expression[i])\n",
    "                ans = calc(ans)\n",
    "                #print(ans)\n",
    "                i += 1\n",
    "            return calcFinal(ans),i\n",
    "        \n",
    "        ansDict,_ = helper(expression,0)\n",
    "        #print(ansDict)\n",
    "        ans = list()\n",
    "        for k in sorted(ansDict.keys(),key = lambda x:(-len(x.split('*')),x)):\n",
    "            if ansDict[k] == 0:\n",
    "                continue\n",
    "            if k == '1':\n",
    "                continue\n",
    "            else:\n",
    "                ans.append(str(ansDict[k]) + '*' + k)\n",
    "        if '1' in ansDict and ansDict['1'] != 0:\n",
    "            ans.append(str(ansDict['1']))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Poly:\r\n",
    "    def __init__(self,val:int,vars:dict) -> None:\r\n",
    "        self.val=val\r\n",
    "        self.vars=vars\r\n",
    "    \r\n",
    "    def add(self,other:'Poly'):\r\n",
    "        self.val+=other.val\r\n",
    "        for k,v in other.vars.items():\r\n",
    "            self.vars[k]=self.vars.get(k,0)+v\r\n",
    "\r\n",
    "    \r\n",
    "    def sub(self,other:'Poly'):\r\n",
    "        self.val-=other.val\r\n",
    "        for k,v in other.vars.items():\r\n",
    "            self.vars[k]=self.vars.get(k,0)-v\r\n",
    "\r\n",
    "    def mul(self,other:'Poly'):\r\n",
    "        ret={}\r\n",
    "        val=self.val*other.val\r\n",
    "        for k2,v2 in other.vars.items():\r\n",
    "            v=ret.get(k2,0)+self.val*v2\r\n",
    "            ret[k2]=v\r\n",
    "        for k1,v1 in self.vars.items():\r\n",
    "            v=ret.get(k1,0)+v1*other.val\r\n",
    "            ret[k1]=v\r\n",
    "            for k2,v2 in other.vars.items():\r\n",
    "                kk=tuple(sorted([*k1,*k2]))\r\n",
    "                ret[kk]=ret.get(kk,0)+v1*v2\r\n",
    "        self.vars=ret\r\n",
    "        self.val=val\r\n",
    "    \r\n",
    "    def to_list(self):\r\n",
    "        ret=[]\r\n",
    "        keys=sorted(self.vars.keys(),key=lambda k:(-len(k),k))\r\n",
    "        for key in keys:\r\n",
    "            v=self.vars[key]\r\n",
    "            if v==0:\r\n",
    "                continue\r\n",
    "            ret.append(f'{v}*{\"*\".join(key)}')\r\n",
    "        if self.val:\r\n",
    "            ret.append(str(self.val))\r\n",
    "        return ret\r\n",
    "class Solution:\r\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\r\n",
    "        \r\n",
    "        varmap={x:y for x,y in zip(evalvars,evalints)}\r\n",
    "\r\n",
    "\r\n",
    "        def parse(expr:str):\r\n",
    "            L=len(expr)\r\n",
    "            idx=0\r\n",
    "            buckets=[]\r\n",
    "            symbols=[]\r\n",
    "            # sign=1\r\n",
    "            # def make_poly()\r\n",
    "            # pair_cnt=0\r\n",
    "            while idx<L:\r\n",
    "                if expr[idx]=='(':\r\n",
    "                    # j=idx+1\r\n",
    "                    pair_cnt=1\r\n",
    "                    for j in range(idx+1,L):\r\n",
    "                        if expr[j]=='(':\r\n",
    "                            pair_cnt+=1\r\n",
    "                        elif expr[j]==')':\r\n",
    "                            pair_cnt-=1\r\n",
    "                        if pair_cnt==0:\r\n",
    "                            buckets.append(parse(expr[idx+1:j]))\r\n",
    "                            idx=j+2\r\n",
    "                            break\r\n",
    "                    \r\n",
    "                elif expr[idx] in '+-*':\r\n",
    "                    symbols.append(expr[idx])\r\n",
    "                    idx+=2\r\n",
    "                    continue\r\n",
    "                elif expr[idx].isdigit():\r\n",
    "                    num=0\r\n",
    "                    while idx<L and expr[idx]!=' ':\r\n",
    "                        num=num*10+ord(expr[idx])-ord('0')\r\n",
    "                        idx+=1\r\n",
    "                    buckets.append(Poly(num,{}))\r\n",
    "                    idx+=1\r\n",
    "                else:\r\n",
    "                    j=idx+1\r\n",
    "                    while j<L and expr[j]!=' ':\r\n",
    "                        j+=1\r\n",
    "                    var=expr[idx:j]\r\n",
    "                    if var in varmap:\r\n",
    "                        buckets.append(Poly(varmap[var],{}))\r\n",
    "                    else:\r\n",
    "                        buckets.append(Poly(0,{(var,):1}))\r\n",
    "                    idx=j+1\r\n",
    "                \r\n",
    "                if symbols and symbols[-1]=='*':\r\n",
    "                    p2=buckets.pop()\r\n",
    "                    p1=buckets.pop()\r\n",
    "                    p1.mul(p2)\r\n",
    "                    buckets.append(p1)\r\n",
    "                    symbols.pop()\r\n",
    "            \r\n",
    "            ans=buckets[0]\r\n",
    "            for i,sy in enumerate(symbols):\r\n",
    "                if sy=='+':\r\n",
    "                    ans.add(buckets[i+1])\r\n",
    "                else:\r\n",
    "                    ans.sub(buckets[i+1])\r\n",
    "            return ans\r\n",
    "        \r\n",
    "        p=parse(expression)\r\n",
    "        ret= p.to_list()\r\n",
    "        return ret\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        d = {evalvars[i]:evalints[i] for i in range(len(evalints))}\n",
    "        def mul(d1, d2):#计算两个哈希表乘法\n",
    "            if not d1:\n",
    "                return d2\n",
    "            elif not d2:\n",
    "                return d1\n",
    "            res = {}\n",
    "            for k, v in d1.items():\n",
    "                for k1, v1 in d2.items():\n",
    "                    if not k:\n",
    "                        res[k1] = res.get(k1, 0) + v1 * v   \n",
    "                    elif not k1:\n",
    "                        res[k] = res.get(k, 0) + v1 * v\n",
    "                    else:\n",
    "                        k_ = \"*\".join(sorted(k1.split(\"*\") + k.split(\"*\")))#这里乘法需要将所有子项重新排序\n",
    "                        res[k_] = res.get(k_, 0) + v1 * v\n",
    "            return res\n",
    "        \n",
    "        def add(d1, d2, p):#计算两个哈希表的加减法\n",
    "            for k, v in d2.items():\n",
    "                if p == \"+\":\n",
    "                    d1[k] = d1.get(k, 0) + v\n",
    "                else:\n",
    "                    d1[k] = d1.get(k, 0) - v\n",
    "            return d1\n",
    "                        \n",
    "        def dfs(s1):\n",
    "            s = s1.split()\n",
    "            p = \"+\"#此项是加或者减的标记符号\n",
    "            i = 0\n",
    "            res = {}\n",
    "            while i < len(s):\n",
    "                j = i\n",
    "                tmp = {}\n",
    "                while j < len(s) and s[j] not in \"+-\":#只要没遇到加减就一直继续下去\n",
    "                    if \"(\" in s[j]:#优先处理括号\n",
    "                        k = j + 1\n",
    "                        l = s[j].count(\"(\")\n",
    "                        r = s[j].count(\")\")\n",
    "                        while l > r:\n",
    "                            l += s[k].count(\"(\")\n",
    "                            r += s[k].count(\")\")\n",
    "                            k += 1\n",
    "                        nex = dfs(\" \".join(s[j:k])[1:-1])#将括号去除后继续深搜\n",
    "                        j = k\n",
    "                        tmp = mul(nex, tmp)#由于不存在加减，直接进行乘法即可\n",
    "                    elif s[j] == \"*\":\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        if s[j] in d or all(i in \"0123456789\" for i in s[j]):#如果是数字\n",
    "                            nex = {\"\":int(d.get(s[j], s[j]))}\n",
    "                        else:#如果不是数字\n",
    "                            nex = {s[j]:1}\n",
    "                        tmp = mul(tmp, nex)#不存在加减，继续乘法\n",
    "                        j += 1\n",
    "                i = j\n",
    "                res = add(res, tmp, p)#将乘法和括号处理完毕后进行加减法\n",
    "                if i == len(s):\n",
    "                    return res\n",
    "                else:\n",
    "                    p = s[i]#将加减符号存储\n",
    "                    i += 1\n",
    "            return res\n",
    "        dic = dfs(expression)\n",
    "        res = []\n",
    "        k_list = sorted(dic.keys(), key = lambda x: [-len(x.split(\"*\")), x.split(\"*\")])#按项次数降序，按项字典序升序\n",
    "        if \"\" in k_list:\n",
    "            k_list.remove(\"\")\n",
    "        for k in k_list:\n",
    "            v = dic[k]\n",
    "            if v != 0:\n",
    "                res.append(str(v) + \"*\" + k)\n",
    "        if \"\" in dic and dic[\"\"] != 0:\n",
    "            res.append(str(dic[\"\"]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "from enum import Enum\r\n",
    "import re\r\n",
    "from typing import List, Union\r\n",
    "from copy import deepcopy\r\n",
    "from functools import reduce\r\n",
    "\r\n",
    "\r\n",
    "class Operator(Enum):\r\n",
    "    ADD = \"+\"\r\n",
    "    MUL = \"*\"\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def from_str(s):\r\n",
    "        if s == \"+\":\r\n",
    "            return Operator.ADD\r\n",
    "        elif s == \"*\":\r\n",
    "            return Operator.MUL\r\n",
    "\r\n",
    "    def calc(op, a, b):\r\n",
    "        if op == Operator.ADD:\r\n",
    "            return a + b\r\n",
    "        elif op == Operator.MUL:\r\n",
    "            return a * b\r\n",
    "\r\n",
    "\r\n",
    "class AST:\r\n",
    "    def __init__(self, op: Union[Operator, str, int], left=None, right=None):\r\n",
    "        self.op = op\r\n",
    "        self.left = left\r\n",
    "        self.right = right\r\n",
    "\r\n",
    "        if self.op == Operator.MUL:\r\n",
    "            if isinstance(self.right.op, int):\r\n",
    "                self.left, self.right = self.right, self.left\r\n",
    "\r\n",
    "    def __str__(self) -> str:\r\n",
    "        if isinstance(self.op, Operator):\r\n",
    "            if self.op == Operator.ADD:\r\n",
    "                return f\"{self.left} + {self.right}\"\r\n",
    "            elif self.op == Operator.MUL:\r\n",
    "                if self.left.op == Operator.ADD:\r\n",
    "                    return f\"({self.left}) * {self.right}\"\r\n",
    "                elif self.right.op == Operator.ADD:\r\n",
    "                    return f\"{self.left} * ({self.right})\"\r\n",
    "                else:\r\n",
    "                    return f\"{self.left} * {self.right}\"\r\n",
    "        elif isinstance(self.op, int):\r\n",
    "            if self.op < 0:\r\n",
    "                return f\"({self.op})\"\r\n",
    "            else:\r\n",
    "                return str(self.op)\r\n",
    "        else:\r\n",
    "            return str(self.op)\r\n",
    "\r\n",
    "    def _up_left(self):\r\n",
    "        self.op = self.left.op\r\n",
    "        self.right = self.left.right\r\n",
    "        self.left = self.left.left\r\n",
    "\r\n",
    "    def _up_right(self):\r\n",
    "        self.op = self.right.op\r\n",
    "        self.left = self.right.left\r\n",
    "        self.right = self.right.right\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_c(s: str, i: int, c: set):\r\n",
    "        if i > len(s) - 1:\r\n",
    "            return None\r\n",
    "        if s[i] in c:\r\n",
    "            return s[i], i + 1\r\n",
    "        return None\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_num(s: str, i: int):\r\n",
    "        j = i\r\n",
    "        while j < len(s) and s[j].isdigit():\r\n",
    "            j += 1\r\n",
    "        return int(s[i:j]), j\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_word(s: str, i: int):\r\n",
    "        j = i\r\n",
    "        while j < len(s) and s[j].isalpha():\r\n",
    "            j += 1\r\n",
    "        return s[i:j], j\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_1(s: str, i: int):\r\n",
    "        l, i = AST._parse_2(s, i)\r\n",
    "\r\n",
    "        while True:\r\n",
    "            op = AST._parse_c(s, i, {\"+\", \"-\"})\r\n",
    "\r\n",
    "            if op is None:\r\n",
    "                break\r\n",
    "\r\n",
    "            op, i = op\r\n",
    "\r\n",
    "            r, i = AST._parse_2(s, i)\r\n",
    "            l, i = (\r\n",
    "                AST(\r\n",
    "                    Operator.ADD,\r\n",
    "                    l,\r\n",
    "                    AST(Operator.MUL, AST(-1), r) if op == \"-\" else r,\r\n",
    "                ),\r\n",
    "                i,\r\n",
    "            )\r\n",
    "\r\n",
    "        return l, i\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_2(s: str, i: int):\r\n",
    "        l, i = AST._parse_3(s, i)\r\n",
    "\r\n",
    "        while True:\r\n",
    "            op = AST._parse_c(s, i, {\"*\"})\r\n",
    "\r\n",
    "            if op is None:\r\n",
    "                break\r\n",
    "\r\n",
    "            op, i = op\r\n",
    "\r\n",
    "            r, i = AST._parse_3(s, i)\r\n",
    "            l, i = AST(Operator.from_str(op), l, r), i\r\n",
    "\r\n",
    "        return l, i\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_3(s: str, i: int):\r\n",
    "        if s[i] == \"(\":\r\n",
    "            l, i = AST._parse_1(s, i + 1)\r\n",
    "            assert s[i] == \")\"\r\n",
    "            return l, i + 1\r\n",
    "        else:\r\n",
    "            if s[i].isdigit():\r\n",
    "                num, i = AST._parse_num(s, i)\r\n",
    "                return AST(num), i\r\n",
    "            else:\r\n",
    "                word, i = AST._parse_word(s, i)\r\n",
    "                return AST(word), i\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def parse(s: str):\r\n",
    "        return AST._parse_1(s, 0)[0]\r\n",
    "\r\n",
    "    def expand(self):\r\n",
    "        if isinstance(self.op, Operator):\r\n",
    "            self.left.expand()\r\n",
    "            self.right.expand()\r\n",
    "\r\n",
    "        if self.op == Operator.MUL:\r\n",
    "            l = self.left\r\n",
    "            r = self.right\r\n",
    "            if l.op == Operator.ADD:\r\n",
    "                self.op = Operator.ADD\r\n",
    "                self.left = AST(Operator.MUL, l.left, r)\r\n",
    "                self.right = AST(Operator.MUL, l.right, deepcopy(r))\r\n",
    "            elif self.right.op == Operator.ADD:\r\n",
    "                self.op = Operator.ADD\r\n",
    "                self.left = AST(Operator.MUL, l, r.left)\r\n",
    "                self.right = AST(Operator.MUL, deepcopy(l), r.right)\r\n",
    "\r\n",
    "        if self.op == Operator.ADD:\r\n",
    "            self.left.expand()\r\n",
    "            self.right.expand()\r\n",
    "\r\n",
    "    def fold_const_expr(self):\r\n",
    "        if isinstance(self.op, Operator):\r\n",
    "            self.left.fold_const_expr()\r\n",
    "            self.right.fold_const_expr()\r\n",
    "\r\n",
    "            if isinstance(self.left.op, int) and isinstance(self.right.op, int):\r\n",
    "                self.op = self.op.calc(self.left.op, self.right.op)\r\n",
    "                self.left = None\r\n",
    "                self.right = None\r\n",
    "        else:\r\n",
    "            return\r\n",
    "\r\n",
    "        if self.op == Operator.MUL:\r\n",
    "            if self.left == 0:\r\n",
    "                self.op = 0\r\n",
    "                self.left = None\r\n",
    "                self.right = None\r\n",
    "            elif self.right == 0:\r\n",
    "                self.op = 0\r\n",
    "                self.left = None\r\n",
    "                self.right = None\r\n",
    "\r\n",
    "        if self.op == Operator.MUL:\r\n",
    "            if self.left.op == 1:\r\n",
    "                self._up_right()\r\n",
    "            elif self.right.op == 1:\r\n",
    "                self._up_left()\r\n",
    "\r\n",
    "        if self.op == Operator.ADD:\r\n",
    "            if self.left.op == 0:\r\n",
    "                self._up_right()\r\n",
    "            elif self.right.op == 0:\r\n",
    "                self._up_left()\r\n",
    "\r\n",
    "    def split_by_add(self):\r\n",
    "        if self.op == Operator.ADD:\r\n",
    "            return self.left.split_by_add() + self.right.split_by_add()\r\n",
    "        else:\r\n",
    "            return [self]\r\n",
    "\r\n",
    "    def split_by_mul(self):\r\n",
    "        if self.op == Operator.MUL:\r\n",
    "            return self.left.split_by_mul() + self.right.split_by_mul()\r\n",
    "        else:\r\n",
    "            return [self]\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def basicCalculatorIV(\r\n",
    "        self, expression: str, evalvars: List[str], evalints: List[int]\r\n",
    "    ) -> List[str]:\r\n",
    "        for i in range(len(evalvars)):\r\n",
    "            expression = re.sub(\r\n",
    "                rf\"\\b{evalvars[i]}\\b\",\r\n",
    "                evalints[i].__str__() if evalints[i] >= 0 else f\"(0 - {-evalints[i]})\",\r\n",
    "                expression,\r\n",
    "            )\r\n",
    "        expression = re.sub(r\"\\s+\", \"\", expression)\r\n",
    "\r\n",
    "        ast = AST.parse(expression)\r\n",
    "        ast.fold_const_expr()\r\n",
    "        ast.expand()\r\n",
    "        ast.fold_const_expr()\r\n",
    "        print(ast)\r\n",
    "\r\n",
    "        add = ast.split_by_add()\r\n",
    "        mul = [a.split_by_mul() for a in add]\r\n",
    "\r\n",
    "        for i in range(len(mul)):\r\n",
    "            mul[i] = sorted(mul[i], key=lambda x: 0 if isinstance(x.op, int) else 1)\r\n",
    "            a = [x for x in mul[i] if isinstance(x.op, int)]\r\n",
    "            a = reduce(lambda x, y: x * y, [x.op for x in a], 1)\r\n",
    "            b = [x for x in mul[i] if not isinstance(x.op, int)]\r\n",
    "            s = sorted(map(str, b))\r\n",
    "            mul[i] = (a, s, \"*\".join(s))\r\n",
    "\r\n",
    "        mul = sorted(mul, key=lambda x: (-x[1].__len__(), x[2]))\r\n",
    "        print(mul)\r\n",
    "\r\n",
    "        stat = {}\r\n",
    "\r\n",
    "        for m in mul:\r\n",
    "            if m[2] in stat:\r\n",
    "                stat[m[2]] += m[0]\r\n",
    "            else:\r\n",
    "                stat[m[2]] = m[0]\r\n",
    "\r\n",
    "        ret = []\r\n",
    "        for k, v in stat.items():\r\n",
    "            if v == 0:\r\n",
    "                continue\r\n",
    "            if k:\r\n",
    "                ret.append(f\"{v}*{k}\")\r\n",
    "            else:\r\n",
    "                ret.append(str(v))\r\n",
    "\r\n",
    "        print(ret)\r\n",
    "\r\n",
    "        return ret\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "from enum import Enum\r\n",
    "import re\r\n",
    "from typing import List, Union\r\n",
    "from copy import deepcopy\r\n",
    "from functools import reduce\r\n",
    "\r\n",
    "\r\n",
    "class Operator(Enum):\r\n",
    "    ADD = \"+\"\r\n",
    "    MUL = \"*\"\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def from_str(s):\r\n",
    "        if s == \"+\":\r\n",
    "            return Operator.ADD\r\n",
    "        elif s == \"*\":\r\n",
    "            return Operator.MUL\r\n",
    "\r\n",
    "    def calc(op, a, b):\r\n",
    "        if op == Operator.ADD:\r\n",
    "            return a + b\r\n",
    "        elif op == Operator.MUL:\r\n",
    "            return a * b\r\n",
    "\r\n",
    "\r\n",
    "class AST:\r\n",
    "    def __init__(self, op: Union[Operator, str, int], left=None, right=None):\r\n",
    "        self.op = op\r\n",
    "        self.left = left\r\n",
    "        self.right = right\r\n",
    "\r\n",
    "        if self.op == Operator.MUL:\r\n",
    "            if isinstance(self.right.op, int):\r\n",
    "                self.left, self.right = self.right, self.left\r\n",
    "\r\n",
    "    def __str__(self) -> str:\r\n",
    "        if isinstance(self.op, Operator):\r\n",
    "            if self.op == Operator.ADD:\r\n",
    "                return f\"{self.left} + {self.right}\"\r\n",
    "            elif self.op == Operator.MUL:\r\n",
    "                if self.left.op == Operator.ADD:\r\n",
    "                    return f\"({self.left}) * {self.right}\"\r\n",
    "                elif self.right.op == Operator.ADD:\r\n",
    "                    return f\"{self.left} * ({self.right})\"\r\n",
    "                else:\r\n",
    "                    return f\"{self.left} * {self.right}\"\r\n",
    "        elif isinstance(self.op, int):\r\n",
    "            if self.op < 0:\r\n",
    "                return f\"({self.op})\"\r\n",
    "            else:\r\n",
    "                return str(self.op)\r\n",
    "        else:\r\n",
    "            return str(self.op)\r\n",
    "\r\n",
    "    def _up_left(self):\r\n",
    "        self.op = self.left.op\r\n",
    "        self.right = self.left.right\r\n",
    "        self.left = self.left.left\r\n",
    "\r\n",
    "    def _up_right(self):\r\n",
    "        self.op = self.right.op\r\n",
    "        self.left = self.right.left\r\n",
    "        self.right = self.right.right\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_c(s: str, i: int, c: set):\r\n",
    "        if i > len(s) - 1:\r\n",
    "            return None\r\n",
    "        if s[i] in c:\r\n",
    "            return s[i], i + 1\r\n",
    "        return None\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_num(s: str, i: int):\r\n",
    "        j = i\r\n",
    "        while j < len(s) and s[j].isdigit():\r\n",
    "            j += 1\r\n",
    "        return int(s[i:j]), j\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_word(s: str, i: int):\r\n",
    "        j = i\r\n",
    "        while j < len(s) and s[j].isalpha():\r\n",
    "            j += 1\r\n",
    "        return s[i:j], j\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_1(s: str, i: int):\r\n",
    "        l, i = AST._parse_2(s, i)\r\n",
    "\r\n",
    "        while True:\r\n",
    "            op = AST._parse_c(s, i, {\"+\", \"-\"})\r\n",
    "\r\n",
    "            if op is None:\r\n",
    "                break\r\n",
    "\r\n",
    "            op, i = op\r\n",
    "\r\n",
    "            r, i = AST._parse_2(s, i)\r\n",
    "            l, i = (\r\n",
    "                AST(\r\n",
    "                    Operator.ADD,\r\n",
    "                    l,\r\n",
    "                    AST(Operator.MUL, AST(-1), r) if op == \"-\" else r,\r\n",
    "                ),\r\n",
    "                i,\r\n",
    "            )\r\n",
    "\r\n",
    "        return l, i\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_2(s: str, i: int):\r\n",
    "        l, i = AST._parse_3(s, i)\r\n",
    "\r\n",
    "        while True:\r\n",
    "            op = AST._parse_c(s, i, {\"*\"})\r\n",
    "\r\n",
    "            if op is None:\r\n",
    "                break\r\n",
    "\r\n",
    "            op, i = op\r\n",
    "\r\n",
    "            r, i = AST._parse_3(s, i)\r\n",
    "            l, i = AST(Operator.from_str(op), l, r), i\r\n",
    "\r\n",
    "        return l, i\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def _parse_3(s: str, i: int):\r\n",
    "        if s[i] == \"(\":\r\n",
    "            l, i = AST._parse_1(s, i + 1)\r\n",
    "            assert s[i] == \")\"\r\n",
    "            return l, i + 1\r\n",
    "        else:\r\n",
    "            if s[i].isdigit():\r\n",
    "                num, i = AST._parse_num(s, i)\r\n",
    "                return AST(num), i\r\n",
    "            else:\r\n",
    "                word, i = AST._parse_word(s, i)\r\n",
    "                return AST(word), i\r\n",
    "\r\n",
    "    @staticmethod\r\n",
    "    def parse(s: str):\r\n",
    "        return AST._parse_1(s, 0)[0]\r\n",
    "\r\n",
    "    def expand(self):\r\n",
    "        if isinstance(self.op, Operator):\r\n",
    "            self.left.expand()\r\n",
    "            self.right.expand()\r\n",
    "\r\n",
    "        if self.op == Operator.MUL:\r\n",
    "            l = self.left\r\n",
    "            r = self.right\r\n",
    "            if l.op == Operator.ADD:\r\n",
    "                self.op = Operator.ADD\r\n",
    "                self.left = AST(Operator.MUL, l.left, r)\r\n",
    "                self.right = AST(Operator.MUL, l.right, deepcopy(r))\r\n",
    "            elif self.right.op == Operator.ADD:\r\n",
    "                self.op = Operator.ADD\r\n",
    "                self.left = AST(Operator.MUL, l, r.left)\r\n",
    "                self.right = AST(Operator.MUL, deepcopy(l), r.right)\r\n",
    "\r\n",
    "        if self.op == Operator.ADD:\r\n",
    "            self.left.expand()\r\n",
    "            self.right.expand()\r\n",
    "\r\n",
    "    def fold_const_expr(self):\r\n",
    "        if isinstance(self.op, Operator):\r\n",
    "            self.left.fold_const_expr()\r\n",
    "            self.right.fold_const_expr()\r\n",
    "\r\n",
    "            if isinstance(self.left.op, int) and isinstance(self.right.op, int):\r\n",
    "                self.op = self.op.calc(self.left.op, self.right.op)\r\n",
    "                self.left = None\r\n",
    "                self.right = None\r\n",
    "        else:\r\n",
    "            return\r\n",
    "\r\n",
    "        if self.op == Operator.MUL:\r\n",
    "            if self.left == 0:\r\n",
    "                self.op = 0\r\n",
    "                self.left = None\r\n",
    "                self.right = None\r\n",
    "            elif self.right == 0:\r\n",
    "                self.op = 0\r\n",
    "                self.left = None\r\n",
    "                self.right = None\r\n",
    "\r\n",
    "        if self.op == Operator.MUL:\r\n",
    "            if self.left.op == 1:\r\n",
    "                self._up_right()\r\n",
    "            elif self.right.op == 1:\r\n",
    "                self._up_left()\r\n",
    "\r\n",
    "        if self.op == Operator.ADD:\r\n",
    "            if self.left.op == 0:\r\n",
    "                self._up_right()\r\n",
    "            elif self.right.op == 0:\r\n",
    "                self._up_left()\r\n",
    "\r\n",
    "    def split_by_add(self):\r\n",
    "        if self.op == Operator.ADD:\r\n",
    "            return self.left.split_by_add() + self.right.split_by_add()\r\n",
    "        else:\r\n",
    "            return [self]\r\n",
    "\r\n",
    "    def split_by_mul(self):\r\n",
    "        if self.op == Operator.MUL:\r\n",
    "            return self.left.split_by_mul() + self.right.split_by_mul()\r\n",
    "        else:\r\n",
    "            return [self]\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def basicCalculatorIV(\r\n",
    "        self, expression: str, evalvars: List[str], evalints: List[int]\r\n",
    "    ) -> List[str]:\r\n",
    "        for i in range(len(evalvars)):\r\n",
    "            expression = re.sub(\r\n",
    "                rf\"\\b{evalvars[i]}\\b\",\r\n",
    "                evalints[i].__str__() if evalints[i] >= 0 else f\"(0 - {-evalints[i]})\",\r\n",
    "                expression,\r\n",
    "            )\r\n",
    "        expression = re.sub(r\"\\s+\", \"\", expression)\r\n",
    "\r\n",
    "        ast = AST.parse(expression)\r\n",
    "        ast.fold_const_expr()\r\n",
    "        ast.expand()\r\n",
    "        ast.fold_const_expr()\r\n",
    "\r\n",
    "        add = ast.split_by_add()\r\n",
    "        mul = [a.split_by_mul() for a in add]\r\n",
    "\r\n",
    "        for i in range(len(mul)):\r\n",
    "            mul[i] = sorted(mul[i], key=lambda x: 0 if isinstance(x.op, int) else 1)\r\n",
    "            a = [x for x in mul[i] if isinstance(x.op, int)]\r\n",
    "            a = reduce(lambda x, y: x * y, [x.op for x in a], 1)\r\n",
    "            b = [x for x in mul[i] if not isinstance(x.op, int)]\r\n",
    "            s = sorted(map(str, b))\r\n",
    "            mul[i] = (a, s, \"*\".join(s))\r\n",
    "\r\n",
    "        mul = sorted(mul, key=lambda x: (-x[1].__len__(), x[2]))\r\n",
    "\r\n",
    "        stat = {}\r\n",
    "\r\n",
    "        for m in mul:\r\n",
    "            if m[2] in stat:\r\n",
    "                stat[m[2]] += m[0]\r\n",
    "            else:\r\n",
    "                stat[m[2]] = m[0]\r\n",
    "\r\n",
    "        ret = []\r\n",
    "        for k, v in stat.items():\r\n",
    "            if v == 0:\r\n",
    "                continue\r\n",
    "            if k:\r\n",
    "                ret.append(f\"{v}*{k}\")\r\n",
    "            else:\r\n",
    "                ret.append(str(v))\r\n",
    "\r\n",
    "        return ret\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        d = {evalvars[i]:evalints[i] for i in range(len(evalints))}\n",
    "        def mul(d1, d2):#计算两个哈希表乘法\n",
    "            if not d1:\n",
    "                return d2\n",
    "            elif not d2:\n",
    "                return d1\n",
    "            res = {}\n",
    "            for k, v in d1.items():\n",
    "                for k1, v1 in d2.items():\n",
    "                    if not k:\n",
    "                        res[k1] = res.get(k1, 0) + v1 * v   \n",
    "                    elif not k1:\n",
    "                        res[k] = res.get(k, 0) + v1 * v\n",
    "                    else:\n",
    "                        k_ = \"*\".join(sorted(k1.split(\"*\") + k.split(\"*\")))#这里乘法需要将所有子项重新排序\n",
    "                        res[k_] = res.get(k_, 0) + v1 * v\n",
    "            return res\n",
    "        \n",
    "        def add(d1, d2, p):#计算两个哈希表的加减法\n",
    "            for k, v in d2.items():\n",
    "                if p == \"+\":\n",
    "                    d1[k] = d1.get(k, 0) + v\n",
    "                else:\n",
    "                    d1[k] = d1.get(k, 0) - v\n",
    "            return d1\n",
    "                        \n",
    "        def dfs(s1):\n",
    "            s = s1.split()\n",
    "            p = \"+\"#此项是加或者减的标记符号\n",
    "            i = 0\n",
    "            res = {}\n",
    "            while i < len(s):\n",
    "                j = i\n",
    "                tmp = {}\n",
    "                while j < len(s) and s[j] not in \"+-\":#只要没遇到加减就一直继续下去\n",
    "                    if \"(\" in s[j]:#优先处理括号\n",
    "                        k = j + 1\n",
    "                        l = s[j].count(\"(\")\n",
    "                        r = s[j].count(\")\")\n",
    "                        while l > r:\n",
    "                            l += s[k].count(\"(\")\n",
    "                            r += s[k].count(\")\")\n",
    "                            k += 1\n",
    "                        nex = dfs(\" \".join(s[j:k])[1:-1])#将括号去除后继续深搜\n",
    "                        j = k\n",
    "                        tmp = mul(nex, tmp)#由于不存在加减，直接进行乘法即可\n",
    "                    elif s[j] == \"*\":\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        if s[j] in d or all(i in \"0123456789\" for i in s[j]):#如果是数字\n",
    "                            nex = {\"\":int(d.get(s[j], s[j]))}\n",
    "                        else:#如果不是数字\n",
    "                            nex = {s[j]:1}\n",
    "                        tmp = mul(tmp, nex)#不存在加减，继续乘法\n",
    "                        j += 1\n",
    "                i = j\n",
    "                res = add(res, tmp, p)#将乘法和括号处理完毕后进行加减法\n",
    "                if i == len(s):\n",
    "                    return res\n",
    "                else:\n",
    "                    p = s[i]#将加减符号存储\n",
    "                    i += 1\n",
    "            return res\n",
    "        dic = dfs(expression)\n",
    "        res = []\n",
    "        k_list = sorted(dic.keys(), key = lambda x: [-len(x.split(\"*\")), x.split(\"*\")])#按项次数降序，按项字典序升序\n",
    "        if \"\" in k_list:\n",
    "            k_list.remove(\"\")\n",
    "        for k in k_list:\n",
    "            v = dic[k]\n",
    "            if v != 0:\n",
    "                res.append(str(v) + \"*\" + k)\n",
    "        if \"\" in dic and dic[\"\"] != 0:\n",
    "            res.append(str(dic[\"\"]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        d = {evalvars[i]:evalints[i] for i in range(len(evalints))}\n",
    "        def mul(d1, d2):#计算两个哈希表乘法\n",
    "            if not d1:\n",
    "                return d2\n",
    "            elif not d2:\n",
    "                return d1\n",
    "            res = {}\n",
    "            for k, v in d1.items():\n",
    "                for k1, v1 in d2.items():\n",
    "                    if not k:\n",
    "                        res[k1] = res.get(k1, 0) + v1 * v   \n",
    "                    elif not k1:\n",
    "                        res[k] = res.get(k, 0) + v1 * v\n",
    "                    else:\n",
    "                        k_ = \"*\".join(sorted(k1.split(\"*\") + k.split(\"*\")))#这里乘法需要将所有子项重新排序\n",
    "                        res[k_] = res.get(k_, 0) + v1 * v\n",
    "            return res\n",
    "        \n",
    "        def add(d1, d2, p):#计算两个哈希表的加减法\n",
    "            for k, v in d2.items():\n",
    "                if p == \"+\":\n",
    "                    d1[k] = d1.get(k, 0) + v\n",
    "                else:\n",
    "                    d1[k] = d1.get(k, 0) - v\n",
    "            return d1\n",
    "                        \n",
    "        def dfs(s1):\n",
    "            s = s1.split()\n",
    "            p = \"+\"#此项是加或者减的标记符号\n",
    "            i = 0\n",
    "            res = {}\n",
    "            while i < len(s):\n",
    "                j = i\n",
    "                tmp = {}\n",
    "                while j < len(s) and s[j] not in \"+-\":#只要没遇到加减就一直继续下去\n",
    "                    if \"(\" in s[j]:#优先处理括号\n",
    "                        k = j + 1\n",
    "                        l = s[j].count(\"(\")\n",
    "                        r = s[j].count(\")\")\n",
    "                        while l > r:\n",
    "                            l += s[k].count(\"(\")\n",
    "                            r += s[k].count(\")\")\n",
    "                            k += 1\n",
    "                        nex = dfs(\" \".join(s[j:k])[1:-1])#将括号去除后继续深搜\n",
    "                        j = k\n",
    "                        tmp = mul(nex, tmp)#由于不存在加减，直接进行乘法即可\n",
    "                    elif s[j] == \"*\":\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        if s[j] in d or all(i in \"0123456789\" for i in s[j]):#如果是数字\n",
    "                            nex = {\"\":int(d.get(s[j], s[j]))}\n",
    "                        else:#如果不是数字\n",
    "                            nex = {s[j]:1}\n",
    "                        tmp = mul(tmp, nex)#不存在加减，继续乘法\n",
    "                        j += 1\n",
    "                i = j\n",
    "                res = add(res, tmp, p)#将乘法和括号处理完毕后进行加减法\n",
    "                if i == len(s):\n",
    "                    return res\n",
    "                else:\n",
    "                    p = s[i]#将加减符号存储\n",
    "                    i += 1\n",
    "            return res\n",
    "        dic = dfs(expression)\n",
    "        res = []\n",
    "        k_list = sorted(dic.keys(), key = lambda x: [-len(x.split(\"*\")), x.split(\"*\")])#按项次数降序，按项字典序升序\n",
    "        if \"\" in k_list:\n",
    "            k_list.remove(\"\")\n",
    "        for k in k_list:\n",
    "            v = dic[k]\n",
    "            if v != 0:\n",
    "                res.append(str(v) + \"*\" + k)\n",
    "        if \"\" in dic and dic[\"\"] != 0:\n",
    "            res.append(str(dic[\"\"]))\n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
